{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Optimal Account Balancing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minTransfers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最优账单平衡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个表示交易的数组 <code>transactions</code> ，其中 <code>transactions[i] = [from<sub>i</sub>, to<sub>i</sub>, amount<sub>i</sub>]</code> 表示 <code>ID = from<sub>i</sub></code> 的人给&nbsp;<code>ID = to<sub>i</sub></code> 的人共计 <code>amount<sub>i</sub> $</code> 。</p>\n",
    "\n",
    "<p>请你计算并返回还清所有债务的最小交易笔数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [[0,1,10],[2,0,5]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "#0 给 #1 $10 。\n",
    "#2 给 #0 $5 。\n",
    "需要进行两笔交易。一种结清债务的方式是 #1 给 #0 和 #2 各 $5 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "#0 给 #1 $10 。\n",
    "#1 给 #0 $1 。\n",
    "#1 给 #2 $5 。\n",
    "#2 给 #0 $5 。\n",
    "因此，#1 只需要给 #0 $4 ，所有的债务即可还清。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= transactions.length &lt;= 8</code></li>\n",
    "\t<li><code>transactions[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt; 12</code></li>\n",
    "\t<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= amount<sub>i</sub> &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [optimal-account-balancing](https://leetcode.cn/problems/optimal-account-balancing/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [optimal-account-balancing](https://leetcode.cn/problems/optimal-account-balancing/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,10],[2,0,5]]', '[[0,1,10],[1,0,1],[1,2,5],[2,0,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "        # accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        m = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            m[x] -= z\n",
    "            m[y] += z\n",
    "        data = list(m.values())\n",
    "        print(data)\n",
    "        res = inf\n",
    "        n = len(data)\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            if cnt >= res:\n",
    "                return\n",
    "            # 像一个匹配的过程\n",
    "            while i < n and data[i] == 0:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i+1, n):\n",
    "                if data[i] * data[j] < 0:\n",
    "                    data[j] += data[i]\n",
    "                    dfs(i+1, cnt+1)\n",
    "                    data[j] -= data[i]\n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] -= aa\n",
    "            person[tt] += aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "        # def dfs(i, cnt):\n",
    "        #     nonlocal res\n",
    "\n",
    "        #     # break condition\n",
    "        #     if cnt >= res: return \n",
    "        #     if i == len(accounts): # reached the final one\n",
    "        #         res = min(res, cnt)\n",
    "        #         return \n",
    "            \n",
    "        #     #  not yet reached the end\n",
    "        #     while i < len(accounts) and accounts[i] == 0: i+=1 # we skip the sellted posiitons\n",
    "            \n",
    "        #     for j in range(i+1, len(accounts)): # all directions # we settle j with i\n",
    "\n",
    "        #         # valid move\n",
    "        #         if accounts[i] * accounts[j] < 0: # otherwise its meaningless\n",
    "                    \n",
    "        #             accounts[j] += accounts[i]\n",
    "        #             dfs(i+1, cnt+1)\n",
    "        #             accounts[j] -= accounts[i]\n",
    "            \n",
    "        #     return \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    tmp_i = accounts[i]\n",
    "                    accounts[j] += accounts[i]\n",
    "                    accounts[i] = 0\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[i] = tmp_i\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for f, t, a in transactions:\n",
    "            counter[f] -= a \n",
    "            counter[t] += a\n",
    "        debts = [v for v in counter.values() if v != 0]\n",
    "        if not debts:\n",
    "            return 0\n",
    "        n = len(debts)\n",
    "        m = 1 << n\n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break \n",
    "        dp = [float('inf')] * m \n",
    "        dp[0] = 0\n",
    "        for i in range(1, m):\n",
    "            if subsum[i] != 0:\n",
    "                continue \n",
    "            dp[i] = bin(i).count('1') - 1\n",
    "            sub = i \n",
    "            rest = i \n",
    "            while sub > 0:\n",
    "                if dp[sub] != float('inf'):\n",
    "                    dp[i] = min(dp[i], dp[i - sub] + dp[sub])\n",
    "                sub = (sub - 1) & rest \n",
    "        return dp[-1] if dp[-1] != float('inf') else - 1\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        account = {}\n",
    "        \n",
    "        # 计算净债务\n",
    "        for fr, to, amount in transactions:\n",
    "            account[fr] = account.get(fr, 0) - amount\n",
    "            account[to] = account.get(to, 0) + amount\n",
    "\n",
    "        debts = [amount for amount in account.values() if amount != 0]\n",
    "\n",
    "        def dfs(s):\n",
    "            while s < len(debts) and debts[s] == 0:\n",
    "                s += 1\n",
    "            if s == len(debts):\n",
    "                return 0\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for i in range(s + 1, len(debts)):\n",
    "                if debts[s] * debts[i] < 0:\n",
    "                    # 优化交易\n",
    "                    debts[i] += debts[s]\n",
    "                    ans = min(ans, 1 + dfs(s + 1))\n",
    "                    # 回溯\n",
    "                    debts[i] -= debts[s]\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # 全局变量退出递归\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        account = {}\n",
    "        \n",
    "        # 计算净债务\n",
    "        for fr, to, amount in transactions:\n",
    "            account[fr] = account.get(fr, 0) - amount\n",
    "            account[to] = account.get(to, 0) + amount\n",
    "\n",
    "        debts = [amount for amount in account.values() if amount != 0]\n",
    "\n",
    "        def dfs(s):\n",
    "            while s < len(debts) and debts[s] == 0:\n",
    "                s += 1\n",
    "            if s == len(debts):\n",
    "                return 0\n",
    "            \n",
    "            ans = float('inf')\n",
    "            for i in range(s + 1, len(debts)):\n",
    "                if debts[s] * debts[i] < 0:\n",
    "                    # 优化交易\n",
    "                    debts[i] += debts[s]\n",
    "                    ans = min(ans, 1 + dfs(s + 1))\n",
    "                    # 回溯\n",
    "                    debts[i] -= debts[s]\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    tmp_i = accounts[i]\n",
    "                    accounts[j] += accounts[i]\n",
    "                    accounts[i] = 0\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[i] = tmp_i\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "        person = defaultdict(int)\n",
    "        for f, t, a in transactions:\n",
    "            person[f] += a\n",
    "            person[t] -= a\n",
    "\n",
    "        \n",
    "        accounts = list(person.values())\n",
    "\n",
    "        accounts.sort(reverse=True)\n",
    "    \n",
    "        self.res = float('inf')\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): #check if at i-th position, we have cnt\n",
    "\n",
    "            if cnt >= self.res : return # we do not need to go further\n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: # skip case\n",
    "                i += 1\n",
    "\n",
    "            \n",
    "            # break case\n",
    "            if i == len(accounts): # as we need to check i in this iteraction\n",
    "                self.res = min(cnt, self.res)\n",
    "                return \n",
    "            \n",
    "            for j in range(i+1, len(accounts)):\n",
    "                # viable part\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i+1, cnt+1) \n",
    "                    accounts[j] -= accounts[i]\n",
    "            \n",
    "            return \n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for a, b, c in transactions:\n",
    "            counter[a] += c        \n",
    "            counter[b] -= c        \n",
    "        debts = [v for v in counter.values()]\n",
    "        if not debts:\n",
    "            return 0\n",
    "        n = len(debts)\n",
    "        m = 1 << n \n",
    "        dp = [float('inf')] * m     \n",
    "        dp[0] = 0\n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break\n",
    "        for i in range(1, m):\n",
    "            if subsum[i] == 0:\n",
    "                dp[i] = bin(i).count('1') - 1 \n",
    "                sub = i\n",
    "                rest = i\n",
    "                while sub > 0:\n",
    "                    dp[i] = min(dp[i], dp[sub] + dp[i - sub])\n",
    "                    sub = (sub - 1) & rest  \n",
    "        return dp[-1] \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # Calculate the balance for each person\n",
    "        balances = {}\n",
    "        for frm, to, amount in transactions:\n",
    "            if frm not in balances:\n",
    "                balances[frm] = 0\n",
    "            if to not in balances:\n",
    "                balances[to] = 0\n",
    "            balances[frm] -= amount\n",
    "            balances[to] += amount\n",
    "\n",
    "        # Filter out people with zero balance\n",
    "        balances = [balance for balance in balances.values() if balance != 0]\n",
    "\n",
    "        # Backtracking to find minimum transactions\n",
    "        def backtrack(balances, index):\n",
    "            # If we've gone through all the balances, return 0\n",
    "            if index == len(balances):\n",
    "                return 0\n",
    "            # If current person's balance is 0 (settled), move on to the next person\n",
    "            if balances[index] == 0:\n",
    "                return backtrack(balances, index + 1)\n",
    "            \n",
    "            # Try to settle the current person's balance with others\n",
    "            min_trans = float('inf')\n",
    "            for i in range(index + 1, len(balances)):\n",
    "                # If the two balances can be settled (one is positive and one is negative)\n",
    "                if balances[index] * balances[i] < 0:\n",
    "                    # Temporarily settle the debt\n",
    "                    balances[i] += balances[index]\n",
    "                    # Recursively settle the rest\n",
    "                    min_trans = min(min_trans, 1 + backtrack(balances, index + 1))\n",
    "                    # Backtrack (undo the settlement)\n",
    "                    balances[i] -= balances[index]\n",
    "\n",
    "            return min_trans\n",
    "\n",
    "        # Start the backtracking from the first person\n",
    "        return backtrack(balances, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        c=collections.Counter()\n",
    "        for a,b,m in transactions:\n",
    "            c[a]-=m \n",
    "            c[b]+=m\n",
    "        account=[]\n",
    "        for key in c:\n",
    "            if c[key]!=0:\n",
    "                account.append(c[key])\n",
    "        n=len(account)\n",
    "        res=float(\"inf\")\n",
    "        def dfs(i,cnt):\n",
    "            nonlocal res\n",
    "            if cnt>=res:\n",
    "                return \n",
    "            while i<n and account[i]==0:\n",
    "                i+=1\n",
    "            if i==n:\n",
    "                res=min(res,cnt)\n",
    "                return\n",
    "            for j in range(i+1,n):\n",
    "                if account[i]*account[j]<0:\n",
    "                    account[j]+=account[i]\n",
    "                    dfs(i+1,cnt+1)\n",
    "                    account[j]-=account[i]\n",
    "        dfs(0,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        balances = defaultdict(int)\n",
    "        for t in transactions:\n",
    "            balances[t[0]] -= t[2]\n",
    "            balances[t[1]] += t[2]\n",
    "\n",
    "        balances = [v for k, v in balances.items() if v != 0]\n",
    "        accounts = len(balances)\n",
    "        states = 1 << accounts\n",
    "        dp = [0] * states\n",
    "\n",
    "        for i in range(1, states):\n",
    "            b = 0\n",
    "            for j in range(accounts):\n",
    "                if 1 & i >> j > 0:\n",
    "                    b += balances[j]\n",
    "            if b == 0:\n",
    "                dp[i] = bin(i).count(\"1\") - 1\n",
    "                j = (i - 1) & i \n",
    "                while j > 0:\n",
    "                    dp[i] = min(dp[i], dp[j] + dp[i ^ j])\n",
    "                    j = (j - 1) & i\n",
    "            else:\n",
    "                dp[i] = inf\n",
    "        return dp[states - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        accounts = {}\n",
    "        for fromid, toid, amount in transactions:\n",
    "            if not fromid in accounts:\n",
    "                accounts[fromid] = 0\n",
    "            if not toid in accounts:\n",
    "                accounts[toid] = 0\n",
    "            accounts[fromid] -= amount\n",
    "            accounts[toid] += amount\n",
    "        values = list(accounts.values())\n",
    "        min_count = sys.maxsize\n",
    "        \n",
    "        def backtracking(start:int, count: int):\n",
    "            nonlocal min_count\n",
    "            if count >= min_count:\n",
    "                return\n",
    "            while start < len(values) and values[start] == 0:\n",
    "                start += 1\n",
    "            if start == len(values):\n",
    "                min_count = min(min_count, count)\n",
    "                return \n",
    "            for i in range(start + 1, len(values)):\n",
    "                if values[start] * values[i] < 0:\n",
    "                    values[i] += values[start]\n",
    "                    backtracking(start + 1, count + 1)\n",
    "                    values[i] -= values[start]\n",
    "        \n",
    "        backtracking(0, 0)\n",
    "        return min_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "        person = defaultdict(int)\n",
    "        for f, t, a in transactions:\n",
    "            person[f] += a\n",
    "            person[t] -= a\n",
    "\n",
    "        \n",
    "        accounts = list(person.values())\n",
    "\n",
    "        accounts.sort(reverse=True)\n",
    "    \n",
    "        self.res = float('inf')\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): #check if at i-th position, we have cnt\n",
    "\n",
    "            if cnt >= self.res : return # we do not need to go further\n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: # skip case\n",
    "                i += 1\n",
    "\n",
    "            \n",
    "            # break case\n",
    "            if i == len(accounts): # as we need to check i in this iteraction\n",
    "                self.res = min(cnt, self.res)\n",
    "                return \n",
    "            \n",
    "            for j in range(i+1, len(accounts)):\n",
    "                # viable part\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i+1, cnt+1) \n",
    "                    accounts[j] -= accounts[i]\n",
    "            \n",
    "            return \n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "        person = defaultdict(int)\n",
    "        for f, t, a in transactions:\n",
    "            person[f] += a\n",
    "            person[t] -= a\n",
    "\n",
    "        \n",
    "        accounts = list(person.values())\n",
    "\n",
    "        accounts.sort(reverse=True)\n",
    "    \n",
    "        self.res = float('inf')\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): #check if at i-th position, we have cnt\n",
    "\n",
    "            #if cnt >= self.res : return # we do not need to go further\n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: # skip case\n",
    "                i += 1\n",
    "\n",
    "            \n",
    "            # break case\n",
    "            if i == len(accounts): # as we need to check i in this iteraction\n",
    "                self.res = min(cnt, self.res)\n",
    "                return \n",
    "            \n",
    "            for j in range(i+1, len(accounts)):\n",
    "                # viable part\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i+1, cnt+1) \n",
    "                    accounts[j] -= accounts[i]\n",
    "            \n",
    "            return \n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "        person = defaultdict(int)\n",
    "        for f, t, a in transactions:\n",
    "            person[f] += a\n",
    "            person[t] -= a\n",
    "\n",
    "        \n",
    "        accounts = list(person.values())\n",
    "\n",
    "        accounts.sort()\n",
    "    \n",
    "        self.res = float('inf')\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): #check if at i-th position, we have cnt\n",
    "\n",
    "            if cnt >= self.res : return # we do not need to go further\n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: # skip case\n",
    "                i += 1\n",
    "\n",
    "            \n",
    "            # break case\n",
    "            if i == len(accounts): # as we need to check i in this iteraction\n",
    "                self.res = min(cnt, self.res)\n",
    "                return \n",
    "            \n",
    "            for j in range(i+1, len(accounts)):\n",
    "                # viable part\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i+1, cnt+1) \n",
    "                    accounts[j] -= accounts[i]\n",
    "            \n",
    "            return \n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # 全局变量退出递归\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # this is similar to 698\n",
    "\n",
    "        # we maintain a key-value object such that key-person has value outstanding, negative means giving money and positive meaning receiving money\n",
    "        person = defaultdict(int)\n",
    "        for ff, tt, aa in transactions:\n",
    "            person[ff] += aa\n",
    "            person[tt] -= aa\n",
    "\n",
    "        \n",
    "        # all outstanding money\n",
    "        accounts = list(person.values())\n",
    "        accounts.sort()\n",
    "        res = float(\"inf\")\n",
    "        # the problem can be turned in to asking the minimum steps to settle down. the outstanding money aka accounts\n",
    "\n",
    "\n",
    "        person = defaultdict(int)\n",
    "        for f, t, a in transactions:\n",
    "            person[f] += a\n",
    "            person[t] -= a\n",
    "\n",
    "        \n",
    "        accounts = list(person.values())\n",
    "\n",
    "        accounts.sort(reverse=True)\n",
    "    \n",
    "        self.res = float('inf')\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): #check if at i-th position, we have cnt\n",
    "\n",
    "            if cnt >= self.res : return # we do not need to go further\n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: # skip case\n",
    "                i += 1\n",
    "\n",
    "            \n",
    "            # break case\n",
    "            if i == len(accounts): # as we need to check i in this iteraction\n",
    "                self.res = min(cnt, self.res)\n",
    "                return \n",
    "            \n",
    "            for j in range(i+1, len(accounts)):\n",
    "                # viable part\n",
    "                if accounts[i] * accounts[j] < 0:\n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i+1, cnt+1) \n",
    "                    accounts[j] -= accounts[i]\n",
    "            \n",
    "            return \n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return self.res\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        def dfs(i, cnt): # checks if from i-th position, with current cnt times of arrangment, we can settle everything down\n",
    "\n",
    "            nonlocal res\n",
    "            # break condition \n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            \n",
    "\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1 # if there are zeros meaning the i-th position is already settled, we move forward.\n",
    "\n",
    "            \n",
    "            if i == len(accounts): # if i finishes i > the maximal index len() - 1\n",
    "                res = min(res, cnt) # we check\n",
    "                return\n",
    "            \n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operatur\n",
    "                    \n",
    "                    accounts[j] += accounts[i]\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        d = defaultdict(int)\n",
    "        for f,t,a in transactions:\n",
    "            d[f] -= a\n",
    "            d[t] += a\n",
    "        nums = [d[i] for i in d if d[i] != 0]\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "\n",
    "        def dfs(i,cnt):\n",
    "            nonlocal ans\n",
    "            if cnt >= ans:\n",
    "                return\n",
    "            while i < n and nums[i] == 0:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                ans = min(ans,cnt)\n",
    "            else:\n",
    "                for j in range(i + 1,n):\n",
    "                    if nums[j]*nums[i] < 0:\n",
    "                        nums[j] += nums[i]\n",
    "                        dfs(i + 1,cnt + 1)\n",
    "                        nums[j] -= nums[i]\n",
    "        \n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        # 定义 f[i] 表示把集合 i 的所有元素值调整为 0，所需要的最少的还钱次数\n",
    "        n = 12\n",
    "        m = 1<<n\n",
    "        cnt = [0]*n\n",
    "        for f,t,a in transactions:\n",
    "            cnt[f] -= a\n",
    "            cnt[t] += a\n",
    "        f = [0]*m\n",
    "        for s in range(1,m):\n",
    "            total = 0\n",
    "            for i in range(n):\n",
    "                if s&(1<<i): \n",
    "                    total += cnt[i]\n",
    "            if total!=0:\n",
    "                f[s] = float('inf')\n",
    "            else:\n",
    "                f[s] = bin(s).count('1') - 1\n",
    "                i = (s-1)&s\n",
    "                while i>0:\n",
    "                    f[s] = min(f[s], f[i]+f[s^i])\n",
    "                    i = (i-1)&s\n",
    "                pass\n",
    "            pass\n",
    "        return f[m-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        person = defaultdict(int)\n",
    "        for x, y, z in transactions:\n",
    "            person[x] -= z\n",
    "            person[y] += z\n",
    "        # 账号\n",
    "        accounts = list(person.values())\n",
    "       \n",
    "        res = float(\"inf\")\n",
    "\n",
    "        def dfs(i, cnt):\n",
    "            nonlocal res\n",
    "            # res maintain the best, if cnt >= res meaning res is still the best, we do not need to go further\n",
    "            if cnt >= res: return \n",
    "            # 账号为0不考虑\n",
    "            while i < len(accounts) and accounts[i] == 0: i += 1\n",
    "\n",
    "            # 遍历完\n",
    "            if i == len(accounts):\n",
    "                res = min(res, cnt)\n",
    "                return\n",
    "            for j in range(i + 1, len(accounts)):\n",
    "                if accounts[i] * accounts[j] < 0: # only when two person one is owing money and one is giving money, we consider the operature\n",
    "                    # 把 i 的债务抹平，并转移到 j 身上\n",
    "                    tmp_i = accounts[i]\n",
    "                    accounts[j] += accounts[i]\n",
    "                    accounts[i] = 0\n",
    "                    dfs(i + 1, cnt + 1)\n",
    "                    accounts[i] = tmp_i\n",
    "                    accounts[j] -= accounts[i]\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for f, t, a in transactions:\n",
    "            counter[f] -= a \n",
    "            counter[t] += a\n",
    "        debts = [v for v in counter.values() if v != 0]\n",
    "        if not debts:\n",
    "            return 0\n",
    "        n = len(debts)\n",
    "        m = 1 << n\n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break \n",
    "        dp = [float('inf')] * m \n",
    "        dp[0] = 0\n",
    "        for i in range(1, m):\n",
    "            if subsum[i] != 0:\n",
    "                continue \n",
    "            dp[i] = bin(i).count('1') - 1\n",
    "            sub = i \n",
    "            rest = i \n",
    "            while sub > 0:\n",
    "                if dp[sub] != float('inf'):\n",
    "                    dp[i] = min(dp[i], dp[i - sub] + dp[sub])\n",
    "                sub = (sub - 1) & rest \n",
    "        return dp[-1] if dp[-1] != float('inf') else - 1\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for f, t, a in transactions:\n",
    "            counter[f] += a \n",
    "            counter[t] -= a \n",
    "        debts = list([b for b in counter.values() if b != 0])\n",
    "        if not debts:\n",
    "            return 0\n",
    "        n = len(debts)\n",
    "        m = 1 << n \n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break \n",
    "        dp = [float('inf')] * m  \n",
    "        dp[0] = 0 \n",
    "        for i in range(1, m):\n",
    "            if subsum[i] != 0:\n",
    "                continue \n",
    "            dp[i] = bin(i).count('1') - 1\n",
    "            rest = i\n",
    "            sub = i \n",
    "            while sub > 0:\n",
    "                dp[i] = min(dp[i], dp[sub] + dp[i - sub])\n",
    "                sub = (sub - 1) & rest \n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for f, t, a in transactions:\n",
    "            counter[f] -= a \n",
    "            counter[t] += a\n",
    "        debts = list([v for v in counter.values() if v != 0])\n",
    "        if not debts:\n",
    "            return 0\n",
    "        n = len(debts)\n",
    "        m = 1 << n \n",
    "        dp = [float('inf')] * m \n",
    "        dp[0] = 0\n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break \n",
    "        for i in range(1, m):\n",
    "            if subsum[i] != 0:\n",
    "                continue \n",
    "            dp[i] = bin(i).count('1') - 1 \n",
    "            rest = i \n",
    "            sub = i\n",
    "            while sub > 0:\n",
    "                dp[i] = min(dp[i], dp[sub] + dp[i - sub])\n",
    "                sub = (sub - 1) & rest \n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        counter = collections.Counter()\n",
    "        for f, t, a in transactions:\n",
    "            counter[f] -= a \n",
    "            counter[t] += a \n",
    "        debts = [v for v in counter.values() if v != 0]\n",
    "        n = len(debts)\n",
    "        if not n:\n",
    "            return 0 \n",
    "        m = 1 << n \n",
    "        subsum = [0] * m \n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    subsum[i] = subsum[i - (1 << j)] + debts[j]\n",
    "                    break \n",
    "        dp = [float('inf')] * m \n",
    "        dp[0] = 0\n",
    "        for i in range(1, m):\n",
    "            if subsum[i] == 0:\n",
    "                dp[i] = bin(i).count('1') - 1 \n",
    "                sub = i \n",
    "                rest = i \n",
    "                while sub > 0:\n",
    "                    if dp[sub] != float('inf'):\n",
    "                        dp[i] = min(dp[i], dp[sub] + dp[i - sub])\n",
    "                    sub = (sub - 1) & rest \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        deg = defaultdict(int)\n",
    "        for u, v, w in transactions:\n",
    "            deg[u] += w\n",
    "            deg[v] -= w\n",
    "        nums = [deg[i] for i in deg if deg[i] != 0]\n",
    "        n = len(nums)\n",
    "\n",
    "        subsum = [0] * (1 << n)\n",
    "        for i in range(n):\n",
    "            for pre in range(1 << i):\n",
    "                subsum[pre | (1 << i)] = subsum[pre] + nums[i]\n",
    "\n",
    "        dp = [0] * (1 << n)  # 最多能分成多少个集合 使得每个集合的和为0\n",
    "        for state in range(1 << n):\n",
    "            g1, g2 = state, 0\n",
    "            while g1:\n",
    "                dp[state] = max(dp[state], int(subsum[g1] == 0) + dp[g2])\n",
    "                g1 = (g1 - 1) & state\n",
    "                g2 = state ^ g1\n",
    "        return n - dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minTransfers(self, transactions: List[List[int]]) -> int:\n",
    "        deg = defaultdict(int)\n",
    "        for u, v, w in transactions:\n",
    "            deg[u] += w\n",
    "            deg[v] -= w\n",
    "        nums = [deg[i] for i in deg if deg[i] != 0]\n",
    "        n = len(nums)\n",
    "\n",
    "        subsum = [0] * (1 << n)\n",
    "        for i in range(n):\n",
    "            for pre in range(1 << i):\n",
    "                subsum[pre | (1 << i)] = subsum[pre] + nums[i]\n",
    "\n",
    "        dp = [0] * (1 << n)  # 最多能分成多少个集合 使得每个集合的和为0\n",
    "        for state in range(1 << n):\n",
    "            g1, g2 = state, 0\n",
    "            while g1:\n",
    "                dp[state] = max(dp[state], int(subsum[g1] == 0) + dp[g2])\n",
    "                g1 = (g1 - 1) & state\n",
    "                g2 = state ^ g1\n",
    "        return n - dp[-1]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
